package com.mj.listen3.链表;

/**
 * https://leetcode-cn.com/problems/merge-two-sorted-lists/
 */
public class _21_合并两个有序链表 {

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 创建虚拟头节点
        ListNode head = new ListNode(0);

        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                l2 = l2.next;
            }
        }

        if (l1 == null) {
            // 把cur全部指向l2
            cur.next = l2;
        } else if (l2 == null) {
            // 把cur全部指向l1
            cur.next = l1;
        }

        return head.next;
    }

    public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;

        // 处理头节点
        ListNode head;
        // 谁的头小谁是新的头
        if (l1.val <= l2.val) {
            head = l1;
            // 指针往后移
            l1 = l1.next;
        } else {
            head = l2;
            // 指针往后移
            l2 = l2.next;
        }

        // 谁的节点小，就链接上谁的节点
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                cur = cur.next;
                // 指针往后移
                l1 = l1.next;
            } else {
                cur.next = l2;
                cur = cur.next;
                // 指针往后移
                l2 = l2.next;
            }
        }

        // 看看哪个链表空了，谁空了，就指向另一个节点
        if (l1 == null) {
            // l1空了，指向l2
            cur.next = l2;
        } else if (l2 == null) {
            // l2空了，指向l1
            cur.next = l1;
        }

        return head;
    }
}
